package trees;

import java.util.LinkedList;

public class BinaryTree<NodeType extends Comparable<NodeType>> implements Tree<NodeType> {

	private BinaryTreeNode root;
	private int size;

	public BinaryTree() {
		size = 0;
	}

	@Override
	public int depth() {
		return depthHelper(root);
	}

	@Override
	public void insert(NodeType element) {
		BinaryTreeNode curNode;

		curNode = root;
		size ++;
		if (curNode == null) {
			root = new BinaryTreeNode();
			root.value = element;
		} else {
			while (true) {
				if (element.compareTo(curNode.value) >= 0) {
					if (curNode.right == null) {
						curNode.right = new BinaryTreeNode();
						curNode.right.value = element;
						return;
					} else {
						curNode = curNode.right;
					}
				} else {
					if (curNode.left == null) {
						curNode.left = new BinaryTreeNode();
						curNode.left.value = element;
						return;
					} else {
						curNode = curNode.left;
					}
				}
			}
		}
	}

	@Override
	public Iterable<NodeType> iterator() {
		LinkedList<NodeType> iterator;
		iterator = new LinkedList<NodeType>();
		iteratorHelper(root, iterator);
		return iterator;
	}

	@Override
	public NodeType remove(NodeType element) {
		BinaryTreeNode curNode, prevNode;
		int comparison, parentComparison;
		NodeType output;

		prevNode = root;
		curNode = root;
		size --; //TODO handle root node deletion
		if (root != null && element.compareTo(root.value) == 0) {
			output = root.value;
			// both children are null, trivial remove case
			if (curNode.right == null && curNode.left == null)
				root = null;
			// one child is null, trivial remove case
			else if (curNode.right == null || curNode.left == null)
				root = root.right == null ? root.left : root.right;
			// both children exist, requires traversal
			else
				if (root.left.hasChildren()) {
					root.value = removeRightMostChild(root.right).value;						
				} else if (root.right.hasChildren()) {
					root.value = removeLeftMostChild(root.right).value;
				} else { // no grandchildren
					root.value = root.right.value;
					root.right = null;
				}
			return output;
		}
		else {
			while (curNode != null) {
				comparison = element.compareTo(curNode.value);
				if (comparison == 0) {
					// both children are null, trivial remove case
					if (curNode.right == null && curNode.left == null) {
						parentComparison = curNode.value.compareTo(prevNode.value);
						if (parentComparison >= 0) 	// curnode is left child of prev
							prevNode.right = null;
						else 						// curnode is right child of prev
							prevNode.left = null;
					}
					// one child is null, trivial remove case
					else if (curNode.right == null || curNode.left == null) {
						parentComparison = curNode.value.compareTo(prevNode.value);
						if (parentComparison >= 0) 	// curnode is right child of prev
							prevNode.right = curNode.left == null ? curNode.right : curNode.left;
						else 						// curnode is left child of prev
							prevNode.left = curNode.left == null ? curNode.right : curNode.left;
					} 
					// both children exist, requires traversal
					else {
						if (curNode.left.hasChildren()) {
							curNode.value = removeRightMostChild(curNode.right).value;						
						} else if (curNode.right.hasChildren()) {
							curNode.value = removeLeftMostChild(curNode.right).value;
						} else { // no grandchildren
							curNode.value = curNode.right.value;
							curNode.right = null;
						}
					}
					return curNode.value;
				} else if (comparison < 0) {
					prevNode = curNode;
					curNode = curNode.left;
				} else {
					prevNode = curNode;
					curNode = curNode.right;
				}
			}
		}
		return null;
	}

	@Override
	public int size() {
		return size;
	}

	private int depthHelper(BinaryTreeNode node) {
		int depth;
		if (node == null)
			return 0;
		depth = 1 + Math.max(depthHelper(node.left), depthHelper(node.right));
		return depth;
	}
	
	private void iteratorHelper(BinaryTreeNode node, LinkedList<NodeType> iterator) {
		if (node == null)
			return;
		iteratorHelper(node.right, iterator);
		iterator.add(node.value);
		iteratorHelper(node.left, iterator);
	}

	/**
	 * Returns the right most child of the input node, and deletes it.
	 * Argument node must have children or null exception will occur
	 */
	private BinaryTreeNode removeRightMostChild(BinaryTreeNode node) {
		BinaryTreeNode output;
		while(node.right.hasChildren()) 
			node = node.right;
		output = node.right;
		node.right = null;
		return output;
	}

	/**
	 * Returns the left most child of the input node, and deletes it.
	 * Argument node must have children or null exception will occur
	 */
	private BinaryTreeNode removeLeftMostChild(BinaryTreeNode node) {
		BinaryTreeNode output;
		while(node.left.hasChildren()) 
			node = node.left;
		output = node.left;
		node.left = null;
		return output;
	}
	
	private class BinaryTreeNode {
		protected BinaryTreeNode left;
		protected BinaryTreeNode right;
		protected NodeType value;
		
		protected boolean hasChildren() {
			return !(left == null && right == null);
		}
	}
	
}
